package sort

/**
冒泡排序只会操作相邻的两个数据。
每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系要求，如果不满足就让它俩互换。
一次冒泡会让至少一个元素移动到它应该在的位置，重复 n 次，就完成了 n 个数据的排序工作。
动态图： https://visualgo.net/zh/sorting

时间复杂度： O(n^2)
空间复杂度：只涉及相邻元素的交换，是原地排序算法
算法稳定性：元素相等不会交换，是稳定的排序算法
 */
func bubbleSort(nums []int) []int {
	if len(nums) <= 1 {
		return nums
	}
	// 冒泡排序核心实现代码
	for i := 0; i < len(nums); i++ {
		flag := false
		for j := 0; j < len(nums) - i - 1; j++ {
			if nums[j] > nums[j+1] {
				nums[j], nums[j+1] = nums[j+1], nums[j]
				flag = true
			}
		}
		// 如果flag为false，说明原本就是有序的
		if !flag {
			break
		}
	}
	return nums
}
